#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-09 10:13 上午
# @Author  : yangdy
# @File    : 2020-10-09.141.环形链表
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 1. python map
        # m = {}
        # while head:
        #     if m.get(head):
        #         return True
        #     m[head] = 1
        #     head = head.next
        # return False
        # 2. slow fast point
        # sp, fp, si = head, head, False
        # while fp:
        #     if si:
        #         sp = sp.next
        #         si = False
        #     else:
        #         si = True
        #     fp = fp.next
        #     if sp == fp:
        #         return True
        # return False
        # 3. 计数 10000
        # count = 0
        # while head and count <= 1000:
        #     count += 1
        #     head = head.next
        # return count > 10000
        # 4. 列表倒置
        if not head or not head.next:
            return False
        p, q = None, head
        while q:
            u, p, q = p, q, q.next
            p.next = u
        return head == q
        # 5. 标记val
        # while head:
        #     if head.val == '1':
        #         return True
        #     head.val = '1'
        #     head = head.next
        # return False



